package ord_list;
import java.util.Comparator;
import java.util.Iterator;
import java.util.ListIterator;


public class ListUtil {
	
	private static class MyCmp<E extends Comparable<E>> implements Comparator<E> {
		@Override
		public int compare(E o1, E o2) {
			return o1.compareTo(o2);
		}
	}
	
	
	/**
	 * inserts e1 in the ordered list l, 
	 * respecting the natural order of the elements of l. 
	 * Returns true iff the element has been inserted
	 * @param <E>
	 * @param l
	 * @param e
	 */
	public static<E extends Comparable<E>> boolean add(OrderedList<E> l, E e1) {
		return add(l, e1, new MyCmp<E>());
	}
	
	public static<E> boolean add(List<E> l, E e1, Comparator<E> cmp) {
		if (e1==null)
			throw new NullPointerException();
		
		ListIterator<E> it = l.listIterator();

		while (it.hasNext()) {
			int comp = cmp.compare(it.next(), e1);
			
			if (comp < 0)
				continue;
			if (comp > 0) {
				it.previous();
				break;
			} else
				return false;
		}
		
		it.add(e1);
		return true;
	}
	
	/**
	 * inserts all elements returned by the iterator src 
	 * in the ordered list dst, respecting the natural order 
	 * of the elements of dst. 
	 * Returns true iff at least one element has been inserted
	 * @param <E>
	 * @param src
	 * @param dst
	 */
	public static<F extends Comparable<F>, E extends F> boolean addAll(
			Iterable<E> src, OrderedList<F> dst) {		
		boolean ris = false;
		for (F srcEl: src) {
			ris |= add(dst, srcEl);
		}
		return ris;
	}
	
	
	/**
	 * returns the list iterator where the element == el
	 * @param l
	 * @param e1
	 * @return
	 */
	private static<E extends Comparable<E>> ListIterator<E> getElem(OrderedList<E> l, E e1){
		ListIterator<E> it = l.listIterator();
		
		while (it.hasNext()) {
			int ris = it.next().compareTo(e1);
			if (ris == 0) {
				return it;
			}
			if (ris > 0)
				return null;
		}
		
		return null;
	}
	
	/**
	 * returns true iff the ordered list l contains el.
	 * @param <E>
	 * @param l
	 * @param e
	 * @return
	 */
	public static<E extends Comparable<E>> boolean contains(OrderedList<E> l, E e1) {
		return getElem(l, e1) != null;
	}
	
	/***
	 * removes the element el from the ordered list l. 
	 * Returns true iff the element has been removed
	 * @param <E>
	 * @param l
	 * @param e1
	 * @return
	 */
	public static<E extends Comparable<E>> boolean remove(OrderedList<E> l, E e1) {
		ListIterator<E> it = getElem(l, e1);
		if (it == null)
			return false;
		it.remove();
		return true;
	}
	
	/***
	 * returns true iff the two (not necessarily ordered) 
	 * lists l1 and l2 are equals, that is, they are both 
	 * instances of List, have the same size, and same elements 
	 * (possibly null) at the same position
	 * @param <E>
	 * @param src
	 * @param dst
	 * @return
	 */
	public static<E> boolean equals(List<E> src, List<E> dst) {
		if (src == null || dst == null)
			return false;
		if (src == dst)
			return true;
		if (src.size() != dst.size()) 
			return false;
		Iterator<E> srcIt = src.iterator();
		Iterator<E> dstIt = dst.iterator();
		
		while (srcIt.hasNext() && dstIt.hasNext()) {
			E srcE = srcIt.next();
			E dstE = dstIt.next();
			
			if (srcE == null)
				if (dstE == null)
					continue;
				else
					return false;
			
			if (!srcE.equals(dstE))
				return false;
		}
		
		return true;
	}
	
	/***
	 * compares the two (not necessarily ordered) lists l1 and l2 
	 * by using the lexicographical order induced by the natural 
	 * order defined on the elements of the two lists
	 * @param <E>
	 * @param src
	 * @param dst
	 * @return
	 */
	public static<E extends Comparable<E>> int compareTo(List<E> src, List<E> dst) {
		Iterator<E> srcIt = src.iterator();
		Iterator<E> dstIt = dst.iterator();
		
		int ris = 0;
		while (srcIt.hasNext() && dstIt.hasNext()) {
			ris = srcIt.next().compareTo(dstIt.next());
			
			if (ris != 0)
				return ris;
		}
		
		if (!srcIt.hasNext()) {
			if (!dstIt.hasNext())
				return 0;
			return -1;
		}
		
		return 1;			
	}
}